package data_structure.mooc.uf;

/**
 * 第六版并查集
 * 基于第五版并查集的优化
 * 路径压缩：将深度较深的树转化为深度较浅的树
 * 在查询操作时彻底将树压缩为两层
 */
public class UnionFind6 implements UnionFind{
    //parent数组记录的是元素的指向关系，从字节点指向父亲节点
    //有一个元素p，p指向q，则parent[p]=q;
    private int []parent;
    //rank[i]表示i所在树的深度
   private int []rank;

    public UnionFind6(int size){
        parent = new int[size];
        rank=new int[size];
        for (int i = 0; i < size; i++) {
            parent[i]=i;
            rank[i]=1;
        }
    }
    @Override
    public int getSize() {
        return parent.length;
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot=find (p);
        int qRoot=find (q);

        if(pRoot==qRoot){
            return;
        }
        //确定p和q的指向关系
        if(rank[pRoot]<rank[qRoot]){
            parent[pRoot]=qRoot;
        }else if(rank[qRoot]<rank[pRoot]){
            parent[qRoot]=pRoot;
        }else{
            parent[qRoot]=pRoot;
            rank[pRoot]+=1;
        }
    }

    /**
     * 返回元素p的根节点
     * @param p
     * @return
     */
    public int find(int p){
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("Illegal index");
        }
        if(p!=parent[p]){
            parent[p]=find(parent[p]);
        }
        return parent[p];
    }
    @Override
    public boolean isConnected(int p, int q) {
        return find (p)==find (q);
    }
}
